In cryptography, the currently most used public key system is R[ivest-]S[hamir-]A[dleman]. This is a system allowing to sign with a secret private key but this signature can be verified by anyone in possession of the non-secret public key. The RSA system or RSA algorithm requires specially constructed keys to work; in particular, two large prime numbers are required, the product of which is the so-called mod[ulus].
In some countries, laws have been passed giving the digital signature a similar legal status as ordinary signatures; for example, in Germany the “German Digital Signature Law” has been passed giving the digital signature a similar legal status as ordinary signatures. For security reasons, such laws pose a number of requirements on the keys being used, such as with respect to the key length. But also the following more technical requirement is given:
The prime factors or prime numbers p, q of n should have the same order of magnitude but should not be too close together:ε1<|log2(p)−log1(q)|<ε2.
Proposed here as a guide for ε1 and ε2 are ε1≈0.5 and ε2≈30.
The prime factors p and q have to be generated randomly and independently of one another, observing the given constraints (cf. http://regtp.de/imperia/md/content/tech reg t/digsign/141.pdf).
Having a system working in accordance with the German Digital Signature Law is a business necessity, in fact not only for the German market but increasingly for the European and worldwide market.
Generating prime numbers for R[ivest-]S[hamir-]A[dleman] works by generating a random number of sufficient length and then applying the operator “NextPrime” to it. To this approach, there was already known a small improvement, namely to insure that the product of the two primes so produced are precisely of a certain length thus allowing to modify the first few bits of the random numbers.
However, it is a problem to generate primes satisfying the above requirement of the German Digital Signature Law. One approach having been used elsewhere is to produce these random numbers, check if they satisfy the requirement and, if not, produce new random numbers. This can be continued until the produced random number would satisfy all conditions.
Obviously this approach has numerous problems. First of all, it is unclear how long it takes to get good random numbers by chance. Secondly, many random numbers are required (which is a scarce resource in some environments, such as smart cards or certain types of servers). Thirdly, complex software is required to do the necessary computations (which is undesirable for several reasons).
Prior art document US 2004/0049526 A1 refers to a method for generating a random prime number within a predetermined interval; a single value being used to generate prime numbers is pre-calculated and stored.
Prior art article “Off-line/On-line Generation of RSA Keys with Smart Cards” by Nathalie Feyt, Marc Joye, David Naccache, and Pascal Paillier, Second International Workshop for Asian Public Key Infrastructures, Taipei, Taiwan, Oct. 30, 2002, to Nov. 1, 2002, discloses a division of the RSA key generation into two phases.
The first phase is performed off-line, before the input parameters are even known; the second phase is performed on-line by the smart card once the input parameters are known, and is meant to be very fast.
By this known technique, an online generation of RSA keys of arbitrary length is achieved from a small set of seeds computed during the off-line phase. Thus, a mixed offboard/on-board solution is presented where the variable and time-consuming part is performed off-line by producing small seeds being used in the second, fast, on-line part of the generation of the keys themselves.
Another solution according to this prior art article consists in pre-computing values for the primes p, q for various pairs and to store those values in an E[lectrically]E[rasable]P[rogrammable]R[ead]O[nly]M[emory]-like, non volatile memory.
A very natural yet cumbersome solution according to this prior art article consists in precomputing and writing in the card's non-volatile memory a set of integer values such that for each i a P[seudo-]R[andom]N[umber]G[enerator] yields a prime number.
Regarding the technological background of the present invention, reference can be made to prior art document U.S. Pat. No. 5,946,397 revealing a method of cryptography with public key based on the discrete logarithm; a database of random values is formed and these random values are combined to determine exponents for keys.
Prior art document US 2004/0156506 A1 relates to selecting cached RSA keys in response to RSA key requests.
Regarding the technological background of the present invention, further reference can be made to prior art article “Implementation of Fast RSA Key Generation on Smart Cards” by Chenghuai Lu, Andre L. M. dos Santos, and Francisco R. Pimentel, Proceedings of the 2002 ACM symposium on Applied computing, Madrid, Spain.
Starting from the disadvantages and shortcomings as described above, in particular starting from the requirements of certain digital signature laws, such as from the requirements of the German Digital Signature Law, and taking the prior art as discussed into account, an object of the present invention is to further develop a circuit arrangement of the kind as described in the technical field as well as a method of the kind as described in the technical field in order to enable the solution of the problem of creating at least one key, in particular the R[ivest-]S[hamir-]A[dleman] key, satisfying these digital signature laws, in particular satisfying the German Digital Signature Law.